The subject invention relates to a method for the secure communication of messages. More particularly, it relates to a method whereby relatively short messages may be encrypted and communicated with a high degree of security. U.S. Pat. application Ser. No. 628,820, assigned to the assignee of the subject invention and filed on even date herewith, for: METHOD AND APPARATUS FOR THE RELIABLE AUTHENTICATION OF COMMUNICATION; to: J. Pastor, discloses an application of the invention of the subject application which is useful for authenticating messages such as postal indicia.
The following definitions and notations are used in the subject application:
E, D--are a pair of keys used in a "public key" encryption system.
K--is a key used in a "secret key" encryption system.
Keys may be specified by use of subscripts or functional notation as necessary. For example, K.sub.i (t) is the key used by the ith party for transaction t.
E[M]; D[M]; K[M]--represent encryption, using the specified key and the appropriate corresponding encryption technique, of a message M.
E[D[M]]; D[E[m]]; K[K[M]]--represent decryption, using the specified key and the appropriate corresponding encryption technique; of the encrypted message M.
(M1, E[P])--represents an unencrypted message comprising the specified elements. Note elements may have been previously encrypted.
{a'}--represents a set of numbers or values.
Hard/easy--as applied to a computation refer to the relation between the cost of the computation and the value of the result. A computation is "hard" if the cost of performing it, using the best available algorithm, is substantially greater than the value of the result. (Those skilled in the art will recognize that the above definition differs from that normally used in complexity theory. The above definition is preferred in the context of the subject which is directed to the protection of the information value of messages rather than theoretical considerations of complexity.)
The "order of a number or variable refers to the number of digits, or bits, needed to express the number or the greatest allowed value of the variable.)
The DES encryption technique is an encryption technique which was developed by the National Bureau Standards, and is in wide spread use, particularly in the financial industry for the secure transfer of funds by wire. DES encrypts information in 64 bit blocks using a secret encryption key, also of the order of 64 bits, and decrypts the information using the same key. DES is well known in the art and a further description will not be necessary for an understanding of the subject invention.
Recently questions have been raised as to the security of the DES technique and another, more secure, technique for encryption, the RSA technique, has been developed. In this technique an encryption key pair E,D is provided and data encrypted using either key may only be decrypted by the other. Further, it is hard to determine one key from knowledge of the other. For this reason RSA is sometimes known as a "public key" system since knowledge of the key used for encryption may be widely distributed and only the key used for decryption need be kept secret. Like DES, RSA is a well known technique in the art and need not be described further for an understanding of the subject invention.
While highly successful as a method of providing secure transmission of messages RSA suffers from the disadvantage that keys and corresponding blocks of information must be of a relatively high order to provide adequate security. RSA encryption using a key of the order of 30 decimal digits can be broken using a modern super computer in only a few seconds of computing time; and it is believed that adequate security for RSA encryption is achieved only with keys on the order of 150-200 decimal digits. Since the encrypted messages are of the same order as the key used for encryption the resulting minimum order for RSA encrypted messages is substantially larger than the 64 bit block encrypted using DES. This of course is disadvantageous in applications where it is desirable to limit the amount of information transmitted. For example, in the above method co-pending application it is desirable to significantly reduce the amount of information which must be encrypted as part of a postal indicia because of the generally limited space available on a mail piece or label. Also, in many applications it is desirable to reduce the length of transmission in order to decrease the likelihood that the message will be intercepted.
Another secret key encryption technique which may be used in the subject invention and which is significantly more secure than DES and requires a relatively small key (though somewhat larger than a DES key) is the "eliptical logarithm technique". This technique, while not as commonly used as DES is well known in the cryptographic art and is further described in the above mentioned application filed on even date herewith. The eliptical logarithm technique is also described in Kolbitz, Neal; A Course in Number Theory and Cryptography; Chapter VI, Vol. 114, Graduate Texts in Mathematics; Springer-Verlog (1987).
Thus, it is an object of the subject invention to provide a method for the secure communication of messages which provides the security of RSA encryption while substantially reducing the order of the messages which are transmitted.